#include <string>
#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iterator>
#include <chrono>   

using namespace std::chrono;
using Vec = std::vector<std::vector<int>>;


bool **graph;
Vec solutions;
int k=3;
int n;
int count=0;
void readFile();
bool findAllMaximal_k_defective(std::vector<int> &chosenNodes);
bool judgeSat(std::vector<int> const& nodes);
bool judgeConnect(int i,int j);
void printAns(std::vector<int> const& v);



void printAns(std::vector<int> const& v)
{
	count++;
	std::cout <<"NO."<< count << " solution: ";
	for (auto i = v.begin(); i < v.end(); i++)
	{
		std::cout << *i << " ";
	}
	std::cout <<std::endl; 
	
}
int main() {
	readFile();
	std::vector<int> v;
	auto tik = system_clock::now();
	findAllMaximal_k_defective(v);
	auto tok = system_clock::now();
	auto duration = duration_cast<microseconds>(tok - tik);
	std::cout <<  "timeCost:" << double(duration.count()) * microseconds::period::num / microseconds::period::den 
     <<  std::endl;
}

void readFile(){
	std::string input_path = "./data/medium_graph.txt";
	std::ifstream input_stream;
	input_stream.open(input_path);
	int u,v;
	while (!input_stream.eof())
	{
		input_stream >>u >> v;
		n = std::max(u,std::max(v,n));
		// std::cout << u <<" "<< v << std::endl;  
	}
	n++;
	
	graph=(bool**)malloc(sizeof(bool*)*n);  
    for(int i=0;i<n;i++)  
    	graph[i]=(bool*)malloc(sizeof(bool)*n);
	
	input_stream.seekg(std::ios::beg);
	while (!input_stream.eof())
	{
		input_stream >>u >> v;
		graph[u][v]=true;
	}
}

bool findAllMaximal_k_defective(std::vector<int> &chosenNodes)
{
	bool flag1 = judgeSat(chosenNodes);
	bool flag2 = false;

	for (int i = chosenNodes.empty()?0 : *(chosenNodes.end()-1)+1; i < n; i++)
	{
		chosenNodes.push_back(i);
		if (judgeSat(chosenNodes))
		{
			flag2 = true;
			findAllMaximal_k_defective(chosenNodes);
		}
		chosenNodes.pop_back();
		
	}
	if(flag1 == true && flag2 == false){
		bool tag = false;
		for(int i = 0 ;i<solutions.size();i++){
			auto v = solutions.at(i);
			std::vector<int> res;
			std::set_difference(chosenNodes.begin(),chosenNodes.end(),v.begin(),v.end(),std::back_inserter(res));
			if (res.empty())
			{
				tag = true;
				break;
			}
			
		}
		if(tag == false){
			printAns(chosenNodes);
			// std::vector<int> s= new 
			solutions.resize(solutions.size()+1);
			*(solutions.end()-1) = chosenNodes;
		}
	}
	return flag1;
}

bool judgeSat(std::vector<int> const& nodes){
	int len = nodes.size();
	int sum = 0;
	for (int i = 0; i < len; i++)
	{
		for (int j = i; j < len; j++)
		{
			int node1 = nodes.at(i);
			int node2 = nodes.at(j);
			if(judgeConnect(node1,node2)){
				sum++;
			}

		}
		
	}
	int satNum = ((len*(len-1))/2)-k;
	if (sum >= satNum){
		return true;
	}
	return false;
	
}

bool judgeConnect(int i,int j){
	if(graph[i][j] == true || graph[j][i] == true){
		return true;
	}
	return false;
}
